// 递归写法
function mergeSort(arr) {
    // 分而治之
    // 先分
    if (arr.length > 1) {
        //将数组 分成两半 递归进行 直到 数组长度 小于等于 1
        let middle = Math.floor(arr.length / 2),
            left = mergeSort(arr.slice(0, middle)),
            right = mergeSort(arr.slice(middle, arr.length));
        //然后 合并排序
        arr = merge(left, right)
    }
    return arr;
}

function merge(left, right) {
    let res = [];
    // 排序
    while (left.length && right.length)
        res.push(left[0] <= right[0] ? left.shift() : right.shift())

    // 拆分完成后只有两个数进行比较，上面的while只会push一个数进res，所以还需下面两个while把另一个数push进去
    while (left.length)
        res.push(left.shift());
    while (right.length)
        res.push(right.shift());

    return res;
}

var a = [4, 0, 1, 3, 2, 6, 17, 419, 22, 68];
console.log(mergeSort(a));